 1.递归之常见递归调用
   
   递归：函数（方法）直接或间接调用自身。是一种常用的编程技巧 。
   严格来说递归不算一种编程思想，其实最多算是一种编程技巧！！
   1).编程递归现象
   2).生活递归现象
   从前有座山，山里有座庙，庙里有个老和尚，正在给小和 尚讲故事呢！故事是什么呢？
  【从前有座山，山里有座庙， 庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？
  『从前有座山，山里有座庙，庙里有个老和尚，正在给小 和尚讲故事呢！故事是什么呢？……』
   】
   假设你在一个电影院，想知道自己坐在哪一排，但是前面人很多，
       m1 懒得数，便问前一排的人 m2【你坐在哪一排？】，只要把 m2 的答案加一，就是 m1 的排数。
       m2 懒得数，便问前一排的人 m3【你坐在哪一排？】，只要把 m3 的答案加一，就是m2 的排数。
       m3 懒得数，便问前一排的人 m4【你坐在哪一排？】，只要把 m4 的答案加一，就是 m3 的排数。
       ...... 直到问到最前面的一排，最后大家都知道自己在哪一排了

 2.调用过程分析
	 
   1).函数调用过程
   普通函数调用过程
   栈空间其实就是内存保存的是当前调用方法的一些局部变量！！
package com.lg.resursion;

public class Demo2 {
    public static void main(String[] args) {
        f1(1);
        f2(3);
    }
// 关注栈空间执行过程

    /**
     * 1.普通函数调用过程
     */
    static void f1(int n){

    }

    static void f2(int n){
        f3(n);
    }

    static void f3(int n){

    }
}   
       递归调用过程
    public static void main(String[] args) { 
        sum(4); 
    }
    static int sum(int n){
        if(n <=1) return n;
        return n+sum(n-1); 
    }
       栈空间示意图
   为什么递归调用我们考虑空间复杂度，因为在执行最后一步之前，其余调用都没有释放！！所以是占用这栈的内存空
间！！
   备注：普通函数调用为何不讨论空间复杂度？（O(1)）常数级别！！
    Stack Overflow
   如果递归调用过程一直没有终止，则栈空间会被一直占用并不断消耗宝贵的空间资源！！最终导致导致栈内存溢出
   (Stack Overflow);
   递归基
   结合上面的分析，如果要进行递归调用，一定要考虑明确一个结束递归的条件，这个条件一般被称为边界条件或者递
归基。
   2).例题--累加和
   计算1+2+3+4+。。。+(n-1)+n的和，(n >0)
      方式1
   public static void main(String[] args) {
	   sum(4);
   }
   static int sum(int n){
	 if(n <=1) return n;
     return n+sum(n-1);
   }
   分析复杂度
   时间复杂度：O(n)
   空间复杂度：O(n)
   备注
   空间复杂度：O(n),先不讨论对堆空间的占用，比如在方法中调用new 方式创建对象。
       方式2
   //第二种 非递归方式 --> 迭代
    static int sum1(int n){
        int result=0; //来存储累加结果
        // 从1开始累加
        for (int i = 1; i <=n; i++) {
            result= result+i;
        }
        return result;
    }
	复杂度分析
    时间复杂度：O(n)
    空间复杂度：O(1)
	    方式3
	// 第三种 ((n+1)*n)/2
    static int sum2(int n) {
        if (n <= 1) {
            return n;
        }
        return ((n+1)*n)/2;
    }
    复杂度分析
    时间复杂度：O(1)
    空间复杂度：O(1)
	总结
	以上3种方式都能实现，但是从复杂度分析我们知道第三种方式显然复杂度更低，所以第三种是对前两种的优化和效
率的提升！！
    思考
    递归效率不高，为何还使用递归？
    使用递归往往不是为了求得最优解，是为了简化解决问题的思路，代码会更简洁！！
    3).评价算法
	(1).概述
	算法的定义
	算法是用来解决特定问题的一系列的执行步骤
	对于同一个问题可以多种解决方式，也就是同一个问题可以有多种算法可以解决，那我们不禁要问：
        不同的算法她们的效率一样吗？
    答案：使用不同的算法解决同一个问题，效率可能相差非常大！！
	(2).如何评价算法质量
	static int sum1(int n){
        int result=0; //来存储累加结果
        // 从1开始累加
        for (int i = 1; i <=n; i++) {
            result= result+i;
        }
        return result;
    }
	
	static int sum2(int n) {
        if (n <= 1) {
            return n;
        }
        return ((n+1)*n)/2;
    }
	
	上面是计算累加和的案例，使用了两种不同的方式实现，我们如何评价两种方案的执行效率呢？
        比较不同算法对同一组输入数据的处理时间，被称为事后统计法！！
    自己编写时间计算工具测算不同算法执行时间
package com.lg.utils;

import java.text.SimpleDateFormat;
import java.util.Date;

public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");

    public interface Task {
        void execute();
    }

    public static void test(String name, Task task) {
        if (task == null) return;
        name = (name == null) ? "" : ("【" + name + "】");
        System.out.println(name);
        System.out.println("开始：" + fmt.format(new Date()));
        long begin = System.currentTimeMillis();
        task.execute();
        long end = System.currentTimeMillis();
        System.out.println("结束：" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0;
        System.out.println("耗时：" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}


	public static void main(String[] args) {

        // 通过工具类测算不同算法的执行时间
        Times.test("非递归(迭代)方式：", new Times.Task() {
            public void execute() {
                // 执行相关算法
                sum1(2000000);
            }
        });

        Times.test("公式方式：", new Times.Task() {
            public void execute() {
                // 执行相关算法
                sum2(2000000);
            }
        });
    }

   事后统计法缺点
       执行时间取决于硬件以及运行时各种不确定的环境因素(开启很多软件与没开启很多软件)
       必须编写测试代码
       测试数据的选择比较难保证公正性(有些算法数据量小可能快，大了就不行，有些相反)
   通常从以下维度来评估算法的优劣
       正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
       时间复杂度（Time complexity）：估算程序指令的执行次数（执行时间）
       空间复杂度（Space complexity）：估算所需占用的存储空间
   (3).大O表示法(Big O)
   大O表示法的定义：一般用大O表示法来描述算法复杂度，它表示的是算法对于数据规模 n的复杂度(时间复杂度，空
间复杂度)
   示例
   估算程序指令的执行次数，以分号为准，判断语句不算！！，
package com.lg.complex;

public class Demo {
    /* 0 1 2 3 4 5
     * 0 1 1 2 3 5 8 13 ....
     */

    // O(2^n)
    public static int f1(int n) {
        if (n <= 1) return n;
        return f1(n - 1) + f1(n - 2);
    }

    // O(n)
    public static int f2(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }

    public static int f3(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        while (n-- > 1) {
            second += first;
            first = second - first;
        }
        return second;
    }

    public static void main(String[] args) {
        int n = 12;
        System.out.println(f2(n));
        System.out.println(f3(n));
//        TimeTool.check("f1", new Task() {
//            public void execute() {
//                System.out.println(f1(n));
//            }
//        });
//
//        TimeTool.check("f2", new Task() {
//            public void execute() {
//                System.out.println(f2(n));
//            }
//        });
    }

    // 时间复杂度：指定执行次数，指令：代码翻译成为底层的汇编语言的指令
    // 关于判断语句省略不计：代码指的是一个分号就是一句代码
    public static void m1(int n) {

        // 汇编指令
        // 1
        if (n > 10) {
            System.out.println("n > 10");
        } else if (n > 5) { // 2
            System.out.println("n > 5");
        } else {
            System.out.println("n <= 5");
        }
		
		// 空间复杂度：讨论方法内部的局部变量占用的内存空间

        // 1 + 4 + 4 + 4
        // 空间复杂度
        // 只定义了一个变量i，所以是O(1)
        for (int i = 0; i < 4; i++) {
            System.out.println("m");
        }

        // 140000
        // O(1)
        // O(1)
    }

    //空间复杂度 所以是O(1)
    public static void m2(int n) {
        // O(n)
        // 1 + 3n
        for (int i = 0; i < n; i++) {
            System.out.println("m");
        }
    }


    public static void m3(int n) {
        // 1 + 2n + n * (1 + 3n)
        // 1 + 2n + n + 3n^2
        // 3n^2 + 3n + 1
        // O(n^2)
        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("m");
            }
        }
    }


    public static void m4(int n) {
        // 1 + 2n + n * (1 + 45)
        // 1 + 2n + 46n
        // 48n + 1
        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 15; j++) {
                System.out.println("m");
            }
        }
    }

    public static void m5(int n) {
        // 8 = 2^3
        // 16 = 2^4
        // 3 = log2(8)
        // 4 = log2(16)
        // 执行次数 = log2(n)
        // O(logn)
        while ((n = n / 2) > 0) {
            System.out.println("m");
        }
    }

    public static void m6(int n) {
        // log5(n)
        // O(logn)
        while ((n = n / 5) > 0) {
            System.out.println("m");
        }
    }

    public static void m7(int n) {
        // 1 + 2*log2(n) + log2(n) * (1 + 3n)
        // 1 + 3*log2(n) + 2 * nlog2(n)
        // O(nlogn)
        for (int i = 1; i < n; i = i * 2) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("m");
            }
        }
    }

    // 空间复杂度是int[] array = new int[n]; O(n)
    public static void m10(int n) {
        // 3+1+1=3n
        // O(n)
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + c);
        }
    }
}
   以上估算完还是很复杂
   大O表示法的规则：
      忽略常数、系数、低阶
          9 --> O(1)
          2n + 3 --> O(n)
          n2 + 2n + 6 --> O(n2)
          4n3 + 3n2 + 22n + 100 -->O(n3)
          对数阶一般省略底数 log2^n = log2^9 ∗ log9^n 所以 log2^n 、log9^n 统称为 log
          写法上，n3 等价于 n^3
   注意：大O表示法仅仅是一种粗略、近似的分析模型，是一种估算，能帮助我们快速了解一个算法的执行效率   
   常见复杂度
   执行次数           复杂度         术语
   120                 O(1)          常数阶
   3n+3                O(n)          线性阶
   10n^2+2n+6          O(n^2)        平方阶
   40log2(n)+250       O(logn)       对数阶
   30n+3nlog3(n)+150   O(nlogn)      nlogn阶
   n^3+2n^2+2n+10      O(n^3)        立方阶
   2^n                 O(2^n)        指数阶
   
   时间复杂度的优先级
   O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
   复杂度曲线图
   空间复杂度
   空间复杂度是估算大概占用的存储空间
   计算m1,m2,m10为例，最后总结：对于当前的算法程序来说我们更关注的时间复杂度，因为现在硬件资源都很充
足！！！
   // 时间复杂度：指定执行次数，指令：代码翻译成为底层的汇编语言的指令
    // 关于判断语句省略不计：代码指的是一个分号就是一句代码
    public static void m1(int n) {

        // 汇编指令
        // 1
        if (n > 10) {
            System.out.println("n > 10");
        } else if (n > 5) { // 2
            System.out.println("n > 5");
        } else {
            System.out.println("n <= 5");
        }
		
		// 空间复杂度：讨论方法内部的局部变量占用的内存空间

        // 1 + 4 + 4 + 4
        // 空间复杂度
        // 只定义了一个变量i，所以是O(1)
        for (int i = 0; i < 4; i++) {
            System.out.println("m");
        }

    }

    //空间复杂度 所以是O(1)
    public static void m2(int n) {
        // O(n)
        // 1 + 3n
        for (int i = 0; i < n; i++) {
            System.out.println("m");
        }
    }
	
   // 空间复杂度是int[] array = new int[n]; O(n)
    public static void m10(int n) {
        // 3+1+1=3n
        // O(n)
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + c);
        }
    }
   补充：注意大O表示法是估算，所谓的执行次数并不是我们的代码执行次数，因为代码最终都要转为汇编的指令，可
能就不仅仅是我们代码的执行次数了。但是这种差异大家都一样而且是常数级别，所以不影响大O表示法的最终结
果！！
   4).估算斐波那契实现复杂度
package com.lg.fib;

public class FibDemo {
    /**
     * 1 + 2 + 4 + 8 = 20 + 21 + 22 + 23 = 24 − 1 = 2n−1 − 1 = 0.5*2n − 1
     * @param
     * @return
     */
    public static void main(String[] args) {
        System.out.println(f1(4));
        System.out.println(f2(4));
    }

    // 时间复杂度 O(2^n)
	// 空间复杂度：O(n)
    public static int f1(int n) {
        if (n <= 1) return n;
        return f1(n - 1) + f1(n - 2);
    }


    // 时间复杂度:O(n)
	// 空间复杂度：O(1)
    public static int f2(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }
}

   fib递归调用过程分析
   1 + 2 + 4 + 8 = 20 + 21 + 22 + 23 = 24 − 1 = 2n−1 − 1 = 0.5*2n − 1
   时间复杂度是 O(2^n)
   5).算法优化角度
   尽可能少的存储空间
   尽可能少的执行时间
       根据情况，可以 空间换时间(大数据资源充足)
       时间换 空间(微型设备资源有限)
   补充：Leetcode
   https://leetcode.com/
   https://leetcode-cn.com/
   